﻿#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>


/*


广度寻路算法：
	从当前点开始   构建一颗 四叉树
	一层层去拓展 直到遇到终点 或者 下一层没了结束

	当前层一个数组 ，下一层一个数组
	数组切换就是层切换

	如果说找到终点了，或者下一层找不出节点。寻路结束

一定找到最短路径！

深度寻路和广度寻路的区别：
	深度
		需要回退，不一定能找到最佳路径。
		时间复杂度相对低
	广度
		不需要回退，一定能找到最佳路径。
		循环嵌套，时间复杂度高


空旷大地图：深度比较优越
小地图，路线要求高：广度比较优越


*/

#define ROW 10
#define COL 10

#define NOBETTER 0

enum dir{ p_up, p_right, p_down, p_left };


//点结构：
struct Mypoint
{
	int row;
	int col;
};

//四叉树节点结构：
struct treeNode
{
	struct Mypoint				pos;					//当前节点坐标

	struct treeNode*			pParent;				//指向父节点;
	struct treeNode*			pChildarr[4];			//当前节点的孩子;
	int							pChildarrSize;			//当前节点的孩子数
};

//创建树节点的函数：
struct treeNode* create_treeNode(int row, int col);

//判断能不能走的函数：		能走 返回true 否则 返回false
bool  canGo(struct Mypoint pos, int map[ROW][COL], bool isFind[ROW][COL]);

int main()
{
	//定义地图：
	int map[ROW][COL] =
	{
		{0,1,1,1,1,1,1,1,1,1},
		{0,0,0,0,0,0,0,0,0,1},
		{0,1,1,1,1,1,0,1,1,1},
		{0,0,0,0,0,0,0,1,1,1},
		{0,1,1,1,1,1,0,1,1,1},
		{0,0,0,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,0,1},
		{1,0,0,0,0,0,0,0,0,1},
		{1,0,1,1,1,1,1,0,0,1},
		{0,0,0,0,0,0,0,0,1,1}
	};


	//起始点：
	struct Mypoint begainPos = { 0,0 };

	//结束点：
	struct Mypoint endPos = { 9,1 };

	//标记是否走过：
	bool isFind[ROW][COL] = { 0 };

	//标记起点走过：
	isFind[begainPos.row][begainPos.col] = true;

	//创建树节点：起始成为根节点：
	struct treeNode* pRoot = create_treeNode(begainPos.row, begainPos.col);


	//当前层：
	struct treeNode* currentFlots[100] = { pRoot };
	int						currentFlotsSize = 1;

	//下一层：
	struct treeNode* nextFlots[100];
	int			nextFlotsSize = 0;


	//当前点：
	struct treeNode* current = NULL;
	struct treeNode* ptemp = NULL;

	bool isFindEnd = false;

	while (1)
	{
		//找出下一层的所有节点：
		for (int i = 0; i < currentFlotsSize; i++)
		{
			for (int j = 0; j < 4; j++)
			{
				//当前层		某个节点四个方向：
				current = currentFlots[i];

				//新的节点：
				ptemp = create_treeNode(current->pos.row, current->pos.col);
				switch (j)
				{
					//四个方向：
				case p_up:
					ptemp->pos.row--;
					break;
				case p_right:
					ptemp->pos.col++;
					break;
				case p_down:
					ptemp->pos.row++;
					break;
				case p_left:
					ptemp->pos.col--;
					break;

				}//end of switch (j)

				//判断能不能走：
				if (canGo(ptemp->pos, map, isFind))
				{
					//能走：

					//入树：
							//子认父：
					ptemp->pParent = current;
					//父认子：
					current->pChildarr[current->pChildarrSize] = ptemp;
					current->pChildarrSize++;

					//入下一层数组：
					nextFlots[nextFlotsSize++] = ptemp;

					//标记走过：
					isFind[ptemp->pos.row][ptemp->pos.col] = true;

					//判断是否到达终点，如果是终点，结束：
					if (endPos.row == ptemp->pos.row && endPos.col == ptemp->pos.col)
					{
						isFindEnd = true;
						break;
					}

				}
				else
				{
					//不能走：

					//释放内存：
					free(ptemp);
					ptemp = NULL;

				}
			}//end of for(int j = 0....
			if (isFindEnd)	break;

		}//end of for(int i = 0....
		if (isFindEnd)	break;

		//下一层没了：
		if (0 == nextFlotsSize)	break;

		//test....
		for (int i = 0; i < nextFlotsSize; i++)
		{
			printf("(%d,%d)", nextFlots[i]->pos.row, nextFlots[i]->pos.col);
		}
		printf("\n");


#if NOBETTER
		//切换到下一层：
		for (int i = 0; i < nextFlotsSize; i++)
		{
			currentFlots[i] = nextFlots[i];
		}
		currentFlotsSize = nextFlotsSize;

		//下一层清空：
		for (int i = 0; i < nextFlotsSize; i++)
		{
			nextFlots[i] = NULL;
		}
		nextFlotsSize = 0;
#else
		//切换到下一层：
		// 
		//以后memcpy函数慎用！！！！！！！！！！！！
		memcpy(currentFlots, nextFlots, 2*sizeof(int) * nextFlotsSize);
			//这里有问题，memcpy	不能把nextFlots数组所有的成员拷贝到currentFlots中，他只能拷贝nextFlots数组中下标为0的成员，怎么解决？
				//老子把	sizeof(int) * nextFlotsSize		改成		2 * sizeof(int) * nextFlotsSize	;可能是数组是二维数组，所以每个成员里是两个int类型变量，拷贝空间要是2倍；
		currentFlotsSize = nextFlotsSize;
		//下一层清空：
		memset(nextFlots, 0, 4 * nextFlotsSize);
		nextFlotsSize = 0;

#endif

	}//end if while(1)

	//打印寻路路径：
	if (isFindEnd)
	{
		printf("找到啦\n");

		while (ptemp)
		{
			printf("(%d,%d)", ptemp->pos.row, ptemp->pos.col);

			ptemp = ptemp->pParent;

		}
		printf("\n");

	}
	else
	{
		printf("西西了，没有找到\n");
	}



	while (1);
	return 0;
}

struct treeNode* create_treeNode(int row, int col)
{
	struct treeNode* pNew = malloc(sizeof(struct treeNode));
	if (NULL == pNew)	return NULL;

	memset(pNew, 0, sizeof(struct treeNode));

	pNew->pos.row = row;
	pNew->pos.col = col;

	return pNew;
}


//能走 返回true 否则 返回false
bool  canGo(struct Mypoint pos, int map[ROW][COL], bool isFind[ROW][COL])
{
	//如果越界：
	if (pos.row >= ROW || pos.row < 0|| pos.col >= COL || pos.col < 0)	return false;
	//如果是障碍：
	if (map[pos.row][pos.col])		return false;
	//如果走过：
	if (isFind[pos.row][pos.col])		return false;

	return true;

}


